package com.shuang.dp2;

public class Solution {
    //动态规划
    public int climbStairs(int n) {

        // 因为下面直接对dp[2]操作了，防止下面越界
        if (n <= 1){
            return n;
        }

        //dp[i] 表示爬楼梯到第i层时一共有dp[i]中方法
        int[] dp = new int[n + 1];

        //递推公式
        //dp[i] 是可以用dp[i-1]和dp[i-2]得到的 dp[i-1]肯定是迈一步直接到达dp[i] dp[i-2]肯定是迈两步直接到达d[i] dp[i-2]不能一次迈一步 如果一次迈一步就到达dp[i-1] 再从dp[i-1]迈一步到dp[i]重复了 所以dp[i] = dp[i - 1] + dp[i - 2];

        //初始化dp数组
        dp[0] = 1;//只是为了当n为0时测试提交代码能通过 但是没有意义 题目也是n从一开始的 所以不管dp[0]

        dp[1] = 1;
        dp[2] = 2;

        //根据公式确定遍历顺序 前到后
        for (int i = 3; i <= n; i++){
            dp[i] = dp[i - 1] + dp[i -2];
        }

        return dp[n];
    }
}
